import java.net.InetAddress;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-09-05
 * Time: 22:48
 */

public class Solution {
    public int[] findRightInterval1(int[][] intervals) {
        int n = intervals.length;
        // 记录了 起始位置 和 对应的下标
        int[][] startIntervals = new int[n][2];
        for (int i = 0; i < n; i++) {
            startIntervals[i][0] = intervals[i][0];
            startIntervals[i][1] = i;
        }
        // 根据起始位置进行排序
        Arrays.sort(startIntervals, (o1, o2) -> o1[0] - o2[0]);

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int left = 0;
            int right = n - 1;
            int target = -1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (startIntervals[mid][0] >= intervals[i][1]) {
                    // 注意 target 到底应该 赋值为 哪个， 应该赋值为 哪个下标
                    target = startIntervals[mid][1];
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            ans[i] = target;
        }
        return ans;
    }


    /**
     *  双指针 (类似于莫队思想)
     */
    public int[] findRightInterval2(int[][] intervals) {
        int len = intervals.length;
        int[] ans = new int[len];
        // starts 与 ends 分别记录 起始位置和下标, 结束位置和下标
        int[][] starts = new int[len][2];
        int[][] ends = new int[len][2];
        for (int i = 0;i < len;i++) {
            starts[i][0] = intervals[i][0];
            starts[i][1] = i;
            ends[i][0] = intervals[i][1];
            ends[i][1] = i;
        }
        // 分别根据起始位置和结束位置从小到大排序
        Arrays.sort(starts, (o1, o2) -> o1[0]-o2[0]);
        Arrays.sort(ends, (o1, o2) -> o1[0]-o2[0]);
        // 开始找合适的位置
        // 注意: 这两层循环的时间复杂度为 O(N)
        // 因为 j 一直在递增, 直到 len
        // 因为 我们对 end 进行排序了, 所以 元素的下一个 >= 结束位置的下标一直在递增
        for (int i = 0, j = 0;i < len;i++) {
            int index = ends[i][1];
            while (j < len && starts[j][0] < ends[i][0]) {
                j++;
            }
            ans[index] = j == len ? -1 : starts[j][1];
        }
        return ans;
    }
}
